package likou;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/03/06 14:48
 */

import java.util.Arrays;

/**
 * 503. 下一个更大元素 II
 */
public class _503 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterElements2(new int[]{1,2,4,5,6,5,4,5,1,2,3})));
    }
    public static int[] nextGreaterElements(int[] nums) {
        int left=0;
        int n = nums.length;
        int[] daan = new int[n];

        for(int i=0;i<n;i++){
            left = i+1;
            while(left<n&&nums[left]<=nums[i]){
                left++;
            }
            if(left==n){
                left = 0;
                for(;left<i;left++){
                    if(nums[left]>nums[i]){
                        System.out.println("        "+left+"  "+i+"  "+nums[i]+"  "+nums[left]);
                        break;
                    }
                }
            }
            if(nums[left]>nums[i]){
                System.out.println(left+"  "+i+"  "+nums[i]+"  "+nums[left]);
                daan[i] = nums[left];
                continue;
            }else{
                daan[i]=-1;
            }
        }
        return daan;
    }

    public static int[] nextGreaterElements2(int[] nums) {
        int[] ans = new int[nums.length];
        int[] stack = new int[nums.length + 1];
        stack[0] = -1;
        int top = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (top > 0 && stack[top] <= nums[i]) {
                top--;
            }
            stack[++top] = nums[i];
            System.out.println(nums[i]);
        }
        System.out.println(Arrays.toString(stack));
        for (int i = nums.length - 1; i >= 0; i--) {
            while (top > 0 && stack[top] <= nums[i]) {
                top--;
            }
            ans[i] = stack[top];
            stack[++top] = nums[i];
        }
        return ans;
    }
}
